#include"Double_List.h"
  void Init_DoubleList(DLNode* plist)
{
	assert(plist);

	plist->prior = plist->next = NULL;
}

DLNode* Buy_NewNode(ELEMTYPE val)
{
	DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
	if (!newnode)
		exit(EXIT_FAILURE);

	newnode->data = val;
	newnode->next = newnode->prior = NULL;
}

bool Insert_Head(DLNode* plist, ELEMTYPE val)
{
	assert(plist);

	DLNode* newnode = Buy_NewNode(val);

	newnode->next = plist->next;
	newnode->prior = plist;
	if (plist->next)
		plist->next->prior = newnode;
	plist->next = newnode;
	  
	return true;
}

bool Insert_Tail(DLNode* plist, ELEMTYPE val)
{
	assert(plist);

	DLNode* newnode = Buy_NewNode(val);

	DLNode* pcur = plist;
	while (pcur->next)
		pcur = pcur->next;

	pcur->next = newnode;
	newnode->prior = pcur;

	return true;
}

bool Insert_Pos(DLNode* plist, ELEMTYPE val, int pos)
{
	assert(plist && pos >= 0 && pos <= Get_Length(plist));

	DLNode* newnode = Buy_NewNode(val);

	if (pos == 0)
		return Insert_Head(plist, val);
	else if (pos == Get_Length(plist))
		return Insert_Tail(plist, val);
	else
	{
		int cnt = 0;
		DLNode* pcur = plist;
		while (cnt < pos)
		{
			cnt++;
			pcur = pcur->next;
		}
		newnode->next = pcur->next;
		newnode->prior = pcur;
		pcur->next->prior = newnode;
		pcur->next = newnode;
	}
}

bool Del_Head(DLNode* plist)
{
	assert(plist);

	if (IsEmpty(plist))
		return false;

	DLNode* del = plist->next;

	plist->next = del->next;
	if (del->next)
		del->next->prior = plist;

	free(del);
	del = NULL;

	return true;
}

bool Del_Tail(DLNode* plist)
{
	assert(plist);

	if (IsEmpty(plist))
		return false;

	DLNode* pcur = plist;

	while (pcur->next->next)
		pcur = pcur->next;

	free(pcur->next);
	pcur->next = NULL;

	return true;
}

bool Del_Pos(DLNode* plist, int pos)
{
	assert(plist && pos >= 0 && pos < Get_Length(plist));

	if (pos == 0)
		return Del_Head(plist);
	else if (pos == Get_Length(plist) - 1)
		return Del_Tail(plist);
	else
	{
		int cnt = 0;
		DLNode* pcur = plist;
		while (cnt < pos)
		{
			cnt++;
			pcur = pcur->next;
		}
		DLNode* del = pcur->next;
		del->next->prior = pcur;
		pcur->next = del->next;
		free(del);
		del = NULL;

		return true;
	}
}

bool Del_Val_First(DLNode* plist, ELEMTYPE val)
{
	assert(plist);

	DLNode* del = Search(plist, val);
	if (!del)
		return false;
	
	int pos = 0;
	for (DLNode* pcur = plist; pcur->next != del; pcur = pcur->next)
		pos++;
	return Del_Pos(plist, pos);
}

bool Del_Val_All(DLNode* plist, ELEMTYPE val)
{
	assert(plist);

	while (DLNode* del = Search(plist, val))
		Del_Val_First(plist, val);
	return true;
}

bool IsEmpty(DLNode* plist)
{
	assert(plist);

	return Get_Length(plist) == 0;
}

int Get_Length(DLNode* plist)
{
	assert(plist);

	int cnt = 0;
	for (DLNode* pcur = plist->next; pcur; pcur = pcur->next)
		cnt++;
	return cnt;
}

void Clear(DLNode* plist)
{
	assert(plist);

	Destroy1(plist);
}

void Destroy1(DLNode* plist)
{
	assert(plist);

	while (!IsEmpty(plist))
		Del_Head(plist);
}

void Destroy2(DLNode* plist)
{
	assert(plist);
	DLNode* del = plist->next;
	DLNode* next = NULL;
	while (del)
	{
		next = del->next;
		free(del);
		del = next;
	}
	plist->next = NULL;
}

void Show(DLNode* plist)
{
	assert(plist);

	printf("plist -> ");
	for (DLNode* pcur = plist->next; pcur; pcur = pcur->next)
		printf("%d -> ", pcur->data);
	printf("NULL\n");
}

DLNode* Search(DLNode* plist, ELEMTYPE val)
{
	assert(plist);

	for (DLNode* pcur = plist->next; pcur; pcur = pcur->next)
		if (pcur->data == val)
			return pcur;

	return NULL;
}

int main()
{
	DLNode list;
	Init_DoubleList(&list);
	Insert_Head(&list, 5);
	Insert_Head(&list, 4);
	Insert_Head(&list, 3);
	Insert_Head(&list, 2);
	Insert_Head(&list, 1);
	Show(&list);
	Destroy1(&list);
	Show(&list);


	Insert_Tail(&list, 11);
	Insert_Tail(&list, 22);
	Insert_Tail(&list, 33);
	Insert_Tail(&list, 44);
	Insert_Tail(&list, 55);
	Show(&list);

	Insert_Pos(&list, 11, 0);
	Insert_Pos(&list, 666, 6);
	Insert_Pos(&list, 333, 3);
	Insert_Pos(&list, 11, 5);
	Show(&list);

	//Del_Head(&list);
	//Show(&list);

	//Del_Tail(&list);
	//Show(&list);

	//Del_Pos(&list, 0);
	//Show(&list);
	//Del_Pos(&list, 5);
	//Show(&list);
	//Del_Pos(&list, 3);
	//Show(&list);

	//Del_Val_First(&list, 22);
	//Show(&list);
	//
	//Del_Val_First(&list, 11);
	//Show(&list);

	Del_Val_All(&list, 11);
	Show(&list);

	Destroy2(&list);
	Show(&list);


	return 0;
}